package com.c2b.algorithm.leetcode.base;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/binary-search-tree-iterator/">二叉搜索树迭代器(Binary Search Tree Iterator)</a>
 * <p>实现一个二叉搜索树迭代器类BSTIterator ，表示一个按<a color='blue'>中序遍历</a>二叉搜索树（BST）的迭代器：</p>
 * <ul>
 *     <li>BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。</li>
 *     <li>boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。</li>
 *     <li>int next()将指针向右移动，然后返回指针处的数字。</li>
 * </ul>
 * 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
 * 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
 * <p>
 *     <b>示例：</b>
 * <pre>
 * 示例：
 *      输入
 *          ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
 *          [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
 *      输出
 *          [null, 3, 7, true, 9, true, 15, true, 20, false]
 *      解释
 *          BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
 *          bSTIterator.next();    // 返回 3
 *          bSTIterator.next();    // 返回 7
 *          bSTIterator.hasNext(); // 返回 True
 *          bSTIterator.next();    // 返回 9
 *          bSTIterator.hasNext(); // 返回 True
 *          bSTIterator.next();    // 返回 15
 *          bSTIterator.hasNext(); // 返回 True
 *          bSTIterator.next();    // 返回 20
 *          bSTIterator.hasNext(); // 返回 False
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目在范围 [1, 10^5] 内</li>
 *     <li>0 <= Node.val <= 10^6</li>
 *     <li>最多调用 10^5 次 hasNext 和 next 操作</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/11 16:24
 */
public class LC0173BinarySearchTreeIterator_M {

    static class BSTIterator {

        Deque<TreeNode> stack;

        public BSTIterator(TreeNode root) {
            stack = new LinkedList<>();
            pushElement(root);
        }

        /**
         * 将以当前节点为根节点的树的所有左子节点依次入栈
         */
        private void pushElement(TreeNode node) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }

        public int next() {
            TreeNode currNode = stack.poll();
            pushElement(currNode.right);
            return currNode.val;
        }

        public boolean hasNext() {
            return !stack.isEmpty();
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(7);
        root.left = new TreeNode(3);
        root.right = new TreeNode(15);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(20);

        BSTIterator bstIterator = new BSTIterator(root);
        System.out.println(bstIterator.next());
        System.out.println(bstIterator.next());
        System.out.println(bstIterator.hasNext());
        System.out.println(bstIterator.next());
        System.out.println(bstIterator.hasNext());
        System.out.println(bstIterator.next());
        System.out.println(bstIterator.hasNext());
        System.out.println(bstIterator.next());
        System.out.println(bstIterator.hasNext());
    }
}
